package study.tree;

public class BSTree<T extends Comparable<T>> {

    public class BSTreeNode<T extends  Comparable<T>>{
        public T key;
        public BSTreeNode<T> left;
        public BSTreeNode<T> right;
        public BSTreeNode<T> parent;

        public BSTreeNode(T key) {
            this.key = key;
        }

        public BSTreeNode(T key, BSTreeNode<T> left, BSTreeNode<T> right, BSTreeNode<T> parent) {
            this.key = key;
            this.left = left;
            this.right = right;
            this.parent = parent;
        }
    }

    BSTreeNode<T> mRoot;

    public BSTreeNode<T> insert(BSTreeNode<T> node){
        if(mRoot==null){
            mRoot = node;
            return mRoot;
        }
       BSTreeNode<T> p = mRoot;
        BSTreeNode<T> pp = null;
        while(p!=null){
            pp = p;
            int cmp = node.key.compareTo(p.key);
            if(cmp<0){
                p = p.left;
            }else {
                p = p.right;
            }
        }

        node.parent = pp;
        int cmp = node.key.compareTo(pp.key);
        if(cmp<0){
            pp.left = node;
        }else if(cmp>0){
            pp.right = node;
        }
        return node;
    }


    public BSTreeNode<T> insert(T key){
        BSTreeNode<T> node = new BSTreeNode<>(key);
        return insert(node);
    }


    public BSTreeNode<T> search(BSTreeNode<T> node,T key){
        if(node==null){
            return null;
        }

        int cmp = key.compareTo(node.key);
        if(cmp == 0){
            return node;
        }else if(cmp<0){
            return search(node.left,key);
        }else if(cmp>0){
            return search(node.right,key);
        }

        return null;
    }

    private BSTreeNode<T> maxiumNode(BSTreeNode<T> node){
        if(node.right!=null){
            return maxiumNode(node.right);
        }
        return node;
    }

    private BSTreeNode<T> miniumNode(BSTreeNode<T> node){
        if(node.left!=null){
            return miniumNode(node.left);
        }
        return node;
    }
    private BSTreeNode<T> successor(BSTreeNode<T> node){
        if(node.right!=null){
            return miniumNode(node.right);
        }

        if(node == node.parent.left){
            return node.parent;
        }else if(node == node.parent.right){
            BSTreeNode<T> p = node.parent;
            while(p!=null){
                if(p.left!=null){
                    return p;
                }
                p = p.parent;
            }
        }
        return null;
    }


    private BSTreeNode<T> preccssor(BSTreeNode<T> node){
         if(node.left!=null){
             return maxiumNode(node.left);
         }

         if(node == node.parent.right){
             return node.parent;
         }else if(node ==node.parent.left){
             BSTreeNode<T> p = node.parent;
             while(p!=null){
                 if(p.right!=null){
                     return p;
                 }
                 p = p .parent;

             }
         }
         return null;
    }

    private BSTreeNode<T> remove(BSTreeNode<T> node){
        if(node.left!=null&&node.right!=null){
            BSTreeNode<T> successor = successor(node);
            node.key = successor.key;
            node  = successor;
        }

        BSTreeNode<T> child = null;

        if(node.left!=null){
            child = node.left;
        }else {
            child = node.right;
        }

       if(child!=null){
           child.parent = node.parent;
       }

       if(node.parent==null){
           mRoot = child;
       }else if(node == node.parent.right){
           node.parent.right = child;
       }else {
           node.parent.left  = child;
       }

       return node;


    }
}
